package InterviewTest.q1709_getKthMagicNumber;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Solution_1 {
    /*
    考虑数字的变化规律： 1 3 5 7 9 15 。。。
    使用一个堆来进行记录 一开始将堆放入1 然后每次取出堆顶数字 也就是此时的最小值
    用它来乘3 5 7 然后放回pq （由于可能有重复 所以用set去重）
    这样就能够在k次后找出对应数字
     */
    public int getKthMagicNumber(int k) {
        int ans = 0;
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        set.add(1L);
        pq.offer(1L);

        for (int i = 0; i < k; i++) {
            long cur = pq.poll();
            ans = (int) cur;

            if (set.add(cur * 3)) pq.offer(cur * 3);
            if (set.add(cur * 5)) pq.offer(cur * 5);
            if (set.add(cur * 7)) pq.offer(cur * 7);
        }
        return ans;
    }
}
